import org.junit.jupiter.api.Test;

import java.util.*;

public class FiftyOneToFiftyNine {

    /**
     * 51. N 皇后
     *
     * @param n n个皇后
     */
    @Test
    public ArrayList<List<String>> solveNQueens(int n) {
//        int n = 4;
        ArrayList<List<String>> lists = new ArrayList<>();
        // 初始化每行皇后的数组 数组下标代表第几行，数组的值代表第几列
        int[] answer = new int[n];
        Arrays.fill(answer, -1);
        HashSet<Integer> positiveDiagonal = new HashSet<>();
        HashSet<Integer> diagonal = new HashSet<>();
        HashSet<Integer> vertical = new HashSet<>();
        backtrack(lists, answer, n, 0, positiveDiagonal, diagonal, vertical);
        System.out.println(Arrays.toString(lists.toArray()));
        return lists;
    }

    /**
     * @param lists            最终的答案
     * @param answer           每一行的答案
     * @param n                第几列
     * @param row              第几行
     * @param positiveDiagonal 正对角线 是否有皇后  *下标相差相等*
     * @param diagonal         斜对角线 是否有皇后  *下标相加相等*
     * @param vertical         列是否有皇后
     */
    private void backtrack(ArrayList<List<String>> lists, int[] answer, int n, int row, HashSet<Integer> positiveDiagonal, HashSet<Integer> diagonal, HashSet<Integer> vertical) {
        // 遍历到最后一行就是结果
        if (row == n) {
            ArrayList<String> list = new ArrayList<>();

            for (int i : answer) {
                char[] chars = new char[n];
                Arrays.fill(chars, '.');
                chars[i] = 'Q';
                list.add(new String(chars));
            }
            lists.add(list);
        } else {
            for (int i = 0; i < n; i++) {
                if (vertical.contains(i)) {
                    continue;
                }
                int sum = row + i;
                if (diagonal.contains(sum)) {
                    continue;
                }
                int difference = row - i;
                if (positiveDiagonal.contains(difference)) {
                    continue;
                }
                answer[row] = i;
                vertical.add(i);
                diagonal.add(sum);
                positiveDiagonal.add(difference);
                //查找下一行的数据
                backtrack(lists, answer, n, row + 1, positiveDiagonal, diagonal, vertical);
                // 找完一次答案之后要清空列和正斜对角和斜对角的数据
                answer[row] = -1;
                vertical.remove(i);
                diagonal.remove(sum);
                positiveDiagonal.remove(difference);
            }
        }
    }

    /**
     * 52. N皇后 II
     *
     * @param n n个皇后
     */
    @Test
    public int totalNQueens(int n) {
//        int n = 4;
        ArrayList<List<String>> lists = new ArrayList<>();
        // 初始化每行皇后的数组 数组下标代表第几行，数组的值代表第几列
        int[] answer = new int[n];
        Arrays.fill(answer, -1);
        HashSet<Integer> positiveDiagonal = new HashSet<>();
        HashSet<Integer> diagonal = new HashSet<>();
        HashSet<Integer> vertical = new HashSet<>();
        backtrack(lists, answer, n, 0, positiveDiagonal, diagonal, vertical);
        return lists.size();
    }

    /**
     * 53. 最大子数组和
     */
    @Test
    public void maxSubArray() {
        int[] nums = new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4};
        // 临时可以是最大的值   resul保存最终的结果
        int result = nums[0], temp = 0;
        for (int num : nums) {
            temp = Math.max(num, temp + num);
            result = Math.max(temp, result);
            System.out.println(result);
        }
        // 第二种，使用分治法，待以后不全
    }

    @Test
    public void spiralOrder() {
        ArrayList<Integer> result = new ArrayList<>();
        int[][] matrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
        int column = matrix.length;
        int row = matrix[0].length;
        // 首先明确，每一个元素必须访问一次，所以要算m*n
        int i = column * row;
        int a = 0, b = 0;
        boolean[][] isFind = new boolean[column][row];
        for (int i1 = 0; i1 < i; i1++) {
            result.add(matrix[a][b]);
            // 记录是否访问过
            isFind[a][b] = true;
            int nextA = a++, nextB =  b++;
            // 要记录转弯 五个转弯条件
            if (a == column - 1 || b == row - 1 || a == 0 || b == 0 || isFind[nextA][b]) {

            }
        }
    }
}